package exercise02;

// 最大连续1的个数 III
// k 是能翻转 0 的个数
// 将原问题转化为: 0 的个数不超过 k 的最大子数组
public class Day230709 {
    // 暴力解法
    public int longestOnes(int[] nums, int k) {
        int n = nums.length;
        int zero = 0;       // 计数 0 的个数
        int maxCount = 0;   // 结果
        for (int left = 0; left < n; left++) {
            int right = left;
            for (; right < n; right++) {
                if(nums[right] == 0) {
                    zero++; // 遇到 0, 计数器 + 1
                }
                if (zero > k) {
                    break;  // 0 的个数超过 k
                }
            }
            zero = 0;
            maxCount = Math.max(maxCount, right - left);
        }
        return maxCount;
    }

    // 使用滑动窗口优化
    public int longestOnes2(int[] nums, int k) {
        int n = nums.length;
        int zero = 0;       // 计数 0 的个数
        int maxCount = 0;   // 结果
        int left = 0;
        int right = 0;
        while (right < n) {
            // 进窗口
            if (nums[right] == 0) {
                zero++;
            }
            while (zero > k) {
                // 出窗口
                if (nums[left++] == 0) {
                    zero--;
                }
            }
            maxCount = Math.max(maxCount, right - left + 1);
            right++;
        }
        return maxCount;
    }
}
